Peripheral Component Interconnect (PCI) is a parallel bus architecture developed in 1992 which has become the predominant local bus for personal computers and similar platforms. The implementation of this technology has come close to its practical limits of performance and can not easily be scaled up in frequency or down in voltage. A new architecture utilizing point-to-point transmission, having a higher speed, and which is scalable for future improvements, is known as PCI Express.
The preferred technique for port arbitration between virtual channels (VC) in PCI Express is a weighted round-robin arbitrator. The advantage of the weighted round-robin arbitrator over a non-weighted round-robin arbitrator is that it is still possible to provide priority to one or more of the channels while guaranteeing that the channel having the least priority will still have access to the network. It is common in a weighted round-robin network to utilize a table having a predetermined number of time slots which are then allocated to the various channels that are vying for access to the network. PCI Express, for example, typically used between 32 and 256 time slots. Priority is given to a particular channel by providing it with more of the time slots than other channels, for example, the highest priority channel might receive half of the time slots whereas the remainder of the time slots are divided amongst lower priority channels. Each channel must receive at least a single time slot so that it is guaranteed access to the network. The assigned time slots can be contiguous or non-contiguous, depending upon the needs of a particular system, and this is usually assigned via a software routine.
FIG. 1 illustrates a known weighted round-robin arbitrator generally shown as 100. In this technique, after a packet of data has been sent out, a signal on line 102 advances the 3 bit counter 104 which address a look-up table 120. A 3 bit counter can address up to 8 entries in the look-up table. The output of the look-up table is a queue select signal on line 122 which is input into multiplexers 108, 124 and 128. Multiplexer 108 receives 3 empty flags 114, 116, 118 from queues 0, 1 and 2 respectively. The queue select signal on line 122 selects the queue matching the entry in the look-up table 120. If the selected queue has data to be sent out, the empty flag will show that that particular queue is not empty. The signal POP on line 130 will be multiplexed via multiplexer 128 onto the line 132, 134 or 136, depending on whether queue 142, 140 or 138 respectively, has been selected. On each POP signal, a bit will be transmitted from the queue via multiplexer 124 to the queue output data line 126. If there are 16 bits to a packet, for example, then 16 POP signals will be utilized to produce the 16 bits that is to be transmitted as a packet. If the selected flag indicates that the particular queue which has been selected is empty, the 3 bit counter 104 will continue to be advanced by the signal 102 to generate a different output to access the next entry in look-up table 120. This will continue until a queue having data to be sent out is found. If all the flags 114, 116, 118 show that all queues are empty AND gate 110 will generate a empty signal on line 112 to indicate to the system controller that there is no data to be sent out. Data is loaded into the queues 138, 140, 142 via lines 144, 146 and 148 respectively.
The system shown in FIG. 1 works quite well when there is data in the queue ready to be sent out. Unfortunately, in real life, often a queue will not have data that is ready to be sent out. In the system shown in FIG. 1, it takes the entire clock cycle to reach this determination. Thus, if no data is ready to be sent out from the selected queue, the time slot is lost. Each time the signal 102 changes only a single queue will be assessed for data to be sent out. If the same queue number is utilized in a series of contiguous time slots or the queues assigned to a series of contiguous time slots all contain no data to be sent out, then it will take a considerable amount of time to reach a time slot assigned to a queue that does have data to be sent out, which time is irretrievably lost. For example if channel Ø (queue Ø) has data to be sent out but it is the lowest priority channel having only a single time slot in a 256 slot table, and all other queues do not have data to be sent out, then data will only be sent out once in 256 transitions of the signal 102. This means that 255 of the 256 time slots are wasted and the data from channel Ø will be unnecessarily delayed. Accordingly, there is a need for a weighted round-robin arbitrator that will not waste the time slot when the selected queue is empty.